package code.D1217;

/**
 * author : yeswater
 * date : 2023/12/18
 * 
 * 搜索二维矩阵 II
 * 
 */

public class T240 {
    // 二分
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int r = 0, c = n - 1; // 行 列
        while (r < m && c >= 0) {
            if (matrix[r][c] < target) r++;
            else if(matrix[r][c] > target) c--;
            else return true;
        }
        return false;
    }
    
    // bst 从右下往左上遍历
    public boolean searchMatrix1(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        for(int i = 0; i < m; i++){
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if(matrix[i][mid] <= target) l = mid;
                else r = mid - 1;
            }
            if(matrix[i][r] == target) return true;
        }
        return false;
    }
}
